package com.openess.bigsearch.engine.BTree.util;

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;

import com.openess.bigsearch.engine.utils.sort.BinaryInsertionSort;
import com.openess.bigsearch.engine.utils.sort.BubbleSort;
import com.openess.bigsearch.engine.utils.sort.HeapSort;
import com.openess.bigsearch.engine.utils.sort.InsertionSort;
import com.openess.bigsearch.engine.utils.sort.MergeSort;
import com.openess.bigsearch.engine.utils.sort.QuickSort;
import com.openess.bigsearch.engine.utils.sort.SelectSort;
import com.openess.bigsearch.engine.utils.sort.ShellSort;

public class Arrays {
	public enum Sort {
		BINSERT, BUBBLE, HEAP, INSERT, MERGE, QUICK, SELECT, SHELL
	}

	public static <E> void sort(E[] array, Sort type) {
		sort(array, 0, array.length - 1, type);
	}

	public static <E> void sort(E[] array, Sort type, Comparator<? super E> c) {
		sort(array, 0, array.length - 1, type, c);
	}

	public static <E> void sort(E[] array, int p, int r, Sort type) {
		sort(array, p, r, type, new Comparator<E>() {
			@SuppressWarnings("unchecked")
			@Override
			public int compare(E o1, E o2) {
				return ((Comparable<E>) o1).compareTo(o2);
			}
		});
	}

	/**
	 * 排序
	 * 
	 * @param list
	 * @param type
	 * @param c
	 */
	public static <E> void sort(E[] array, int p, int r, Sort type,
			Comparator<? super E> c) {
		switch (type) {
		case BINSERT:
			new BinaryInsertionSort<E>().sort(array, p, r, c);
			break;
		case BUBBLE:
			new BubbleSort<E>().sort(array, p, r, c);
			break;
		case HEAP:
			new HeapSort<E>().sort(array, p, r, c);
			break;
		case INSERT:
			new InsertionSort<E>().sort(array, p, r, c);
			break;
		case MERGE:
			new MergeSort<E>().sort(array, p, r, c);
			break;
		case QUICK:
			new QuickSort<E>().sort(array, p, r, c);
			break;
		case SELECT:
			new SelectSort<E>().sort(array, p, r, c);
			break;
		case SHELL:
			new ShellSort<E>().sort(array, p, r, c);
			break;
		}
	}

	/**
	 * 利用最大堆来计算一个数组中的最大值，时间复杂度O(n)
	 * 
	 * @param list
	 */
	public static <E> void max(E[] list, Comparator<? super E> c) {
		HeapSort<E> sort = new HeapSort<E>();
		sort.max(list, c);
	}

	/**
	 * 合并两个数组并排序
	 * 
	 * @param list1
	 * @param list2
	 * @return
	 */
	public static Integer[] merge(Integer[] list1, Integer[] list2) {
		Integer[] newList = new Integer[list1.length + list2.length];
		System.arraycopy(list1, 0, newList, 0, list1.length);
		System.arraycopy(list2, 0, newList, list1.length, list2.length);
		Arrays.sort(newList, 0, newList.length, Sort.HEAP);
		return newList;
	}

	/**
	 * 用折半查找指定的值，并返回其下标，或者应该插入的位置，前提：数组已排序
	 * 
	 * @param array
	 * @param key
	 * @return 
	 *         如果返回值>=0说明找到了对应的值。如果返回值小于0说明没找到，返回值=-low-1，low即为应该插入的地方。如果程序错误，那么返回
	 *         -1。
	 */
	public static <E extends Comparable<E>> int binarySearch(E[] array, E key) {
		if (array == null || key == null) {
			return -1;
		}
		int low = 0;
		int high = array.length - 1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (array[mid].compareTo(key) > 0) {
				high = mid - 1;
			} else if (array[mid].compareTo(key) < 0) {
				low = mid + 1;
			} else {
				return mid;
			}
		}
		return -low - 1;
	}

	/**
	 * 计算一个分词在文档中的词频1+log(f)
	 * 
	 * @param num
	 *            分词出现次数
	 * @param totalNum
	 *            文档总词数
	 * @return
	 */
	public static double TF(int num) {
		double result = 1 + Math.log(num);
		return result;
	}

	/**
	 * 计算逆文档频率，idf_k = log(N/nk)
	 * 
	 * @param num
	 *            指定分词出现过的文档数量
	 * @param totalNum
	 *            索引中，文档的总个数
	 * @return
	 */
	public static double IDF(int num, int totalNum) {
		return Math.log((double) totalNum / num);
	}

	/**
	 * 计算向量的模
	 * 
	 * @param tfIdf
	 *            分词特征值组成的数组
	 * @return
	 */
	public static double norm(double... tfIdf) {
		double result = 0;
		for (double temp : tfIdf) {
			result += temp * temp;
		}
		return Math.sqrt(result);
	}

	/**
	 * 依据参数计算一个分词对应的一个文档的BM25值，在多个查询词的情况下，这只是部分分数，还需要把所有分词的分数加起来，才算是一篇文档的最终分数。
	 * 
	 * @param totalNum
	 *            总文档数量
	 * @param docNum
	 *            包含分词的文档数
	 * @param docLength
	 *            文档长度
	 * @param prop
	 *            dl/avdl的比例值
	 * @param dFrq
	 *            分词在文档中的词频
	 * @param qFrq
	 *            分词在查询语句中的词频
	 * @return
	 */
	public static double BM25(int totalNum, int docNum, int docLength,
			double prop, int dFrq, int qFrq) {
		// 在无法区分相关文档的情况下，part1的计算类似于IDF
		double part1 = Math.log((totalNum - docNum + 0.5d) / (docNum + 0.5d));
		double K = 1.2d * (0.25 + 0.75 * prop);
		double part2 = ((1.2d + 1) * dFrq) / (K + dFrq);
		double part3 = ((200 + 1d) * qFrq) / (200d + qFrq);
		return part1 * part2 * part3;
	}

	/**
	 * BM25F模型的部分得分(求和前)
	 * 
	 * @param totalNum
	 * @param docNum
	 * @param fscoreTotal
	 *            是fscore分数的全域求和结果
	 * @return
	 */
	public static double MB25F(int totalNum, int docNum, double fscoreTotal) {
		// 在无法区分相关文档的情况下，part1的计算类似于IDF
		double part1 = Math.log((totalNum - docNum + 0.5d) / (docNum + 0.5d));
		double part2 = fscoreTotal / (1.2 + fscoreTotal);
		return part1 * part2;
	}

	/**
	 * BM25F模型的部分得分(fi部分,未求和)
	 * 
	 * @param fweight
	 * @param ffrq
	 * @param fb
	 * @param flength
	 * @param avflength
	 * @return
	 */
	public static double fscore(double fweight, int ffrq, double bu,
			int flength, int avflength) {
		double Bu = (1 - bu) + bu * flength / avflength;
		double fscore = fweight * ffrq / Bu;
		return fscore;
	}

	/**
	 * 利用排序实现的去重
	 * 
	 * @param array
	 * @return
	 */
	public static <E> E[] repeatFilter(E[] array) {
		return repeatFilter(array, new Comparator<E>() {
			@SuppressWarnings("unchecked")
			@Override
			public int compare(E o1, E o2) {
				return ((Comparable<E>) o1).compareTo(o2);
			}
		});
	}

	/**
	 * 利用排序实现的去重
	 * 
	 * @param array
	 */
	@SuppressWarnings("unchecked")
	public static <E> E[] repeatFilter(E[] array, Comparator<? super E> c) {
		LinkedList<E> list = new LinkedList<E>();
		Arrays.sort(array, Sort.QUICK, c);
		E first = array[0];
		list.add(first);
		for (int i = 1; i < array.length; i++) {
			if (array[i] == null)
				continue;
			E second = array[i];
			if (c.compare(second, first) != 0) {
				first = second;
				list.add(second);
			}
		}
		E[] result = (E[]) java.lang.reflect.Array.newInstance(array.getClass()
				.getComponentType(), list.size());
		return list.toArray(result);
	}

	/**
	 * 利用排序实现的去重
	 * 
	 * @param array
	 */
	@SuppressWarnings("unchecked")
	public static <E extends Comparable<E>> E[] repeatFilter(Collection<E> col,
			Comparator<? super E> c) {
		LinkedList<E> list = new LinkedList<E>();
		Iterator<E> it = col.iterator();
		E[] array = (E[]) java.lang.reflect.Array.newInstance(it.next()
				.getClass(), col.size());
		col.toArray(array);
		Arrays.sort(array, Sort.QUICK, c);
		E first = array[0];
		list.add(first);
		for (int i = 1; i < array.length; i++) {
			if (array[i] == null)
				continue;
			E second = array[i];
			if (second.compareTo(first) != 0) {
				first = second;
				list.add(second);
			}
		}
		E[] result = (E[]) java.lang.reflect.Array.newInstance(array.getClass()
				.getComponentType(), list.size());
		return list.toArray(result);
	}

	/**
	 * 利用排序实现的去重
	 * 
	 * @param array
	 */
	@SuppressWarnings("unchecked")
	public static <E extends Comparable<E>> LinkedList<E> repeatFilter2Link(
			Collection<E> col, Comparator<? super E> c) {
		LinkedList<E> list = new LinkedList<E>();
		Iterator<E> it = col.iterator();
		E[] array = (E[]) java.lang.reflect.Array.newInstance(it.next()
				.getClass(), col.size());
		col.toArray(array);
		Arrays.sort(array, Sort.QUICK, c);
		E first = array[0];
		list.add(first);
		for (int i = 1; i < array.length; i++) {
			if (array[i] == null)
				continue;
			E second = array[i];
			if (second.compareTo(first) != 0) {
				first = second;
				list.add(second);
			}
		}
		return list;
	}
}
